
/*
 * Question: Add a field 'DescNum' into binary
 * tree's node. Try to propose an algorithm to
 * calculate every node's descendant number.
 *
 * Date: 01/26/2012
 */

#include <iostream>
#include "bitree.h"

class bitree : public _bitree<bitree, char>
{
    public:
    int DescNum;
};

int descendant_number(bitree *rt)
{
    int ln, rn;

    if (!rt)
        return 0;
    ln = descendant_number(rt->lchild);
    rn = descendant_number(rt->rchild);
    rt->DescNum = ln + rn;
    return ln+rn+1;
}

void print_tree(bitree *rt)
{
    if (!rt)
        return;
    cout << rt->key << ":\t" << rt->DescNum << endl;
    print_tree(rt->lchild);
    print_tree(rt->rchild);
}

int main()
{
    bitree *rt;

    bitree_create<bitree, char>(rt, "ex55.txt");
    descendant_number(rt);
    print_tree(rt);
    bitree_destory(rt);

    return 0;
 }
